# -*- coding: utf-8 -*-            
# @Time : 2023/8/2 22:04
# @Author  : lining
# @FileName: n叉树的层序遍历.py
"""
一层一层，从左往右遍历，可用队列实现，先进先出
https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
层序遍历，并求层数
          1
    2  3   4   5
6,7,8
1,2,3,4,5,6,7,8,
（1）把根节点放入结果集，把子节点放入中间结果集
（2）取出中间结果集的第一个数据，开始遍历，遇到有子节点就把子节点放入中间结果集
"""


class Node():
    def __init__(self, value=0):
        """
        :param value:
        :param child: 列表形式，可存放多个子节点
        """
        self.value = value
        self.child = []


result = []
s = []


def Traversal(node):
    """
    :param node: 开始访问的节点
    :return:
    """
    if node is None:
        return
    result.append([0,node.value])
    if not node.child:
        return
    s.append(node.child)
    deepth = 1
    while s:
        result.append([deepth])
        current = s[0]
        del s[0]
        for a in current:
            result[deepth].append(a.value)
            if a.child:
                s.append(a.child)
        deepth=deepth+1
    print(result)


node = Node(1)
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(5)
node5 = Node(6)
node6 = Node(7)
node7 = Node(8)
node8 = Node(9)
node9 = Node(10)
node10 = Node(11)
node11 = Node(12)
node12 = Node(13)
node.child.extend([node1,node2,node3,node4])
node2.child.extend([node5,node6,node7,node8])
node6.child.extend([node9,node10,node11,node12])
"""
                          (1)
              2        (3)        4       5
                6     (7)      8    9
                  10,11,12,13
"""
Traversal(node)

